package yongyoubishi;

/**
 * 计算盛水量
 * Created by JiaJia on 2019/9/11 0011.
 */
public class TianShuiTong {
    public static void main(String[] args) {
        int[] num = {0, 1, 0, 1, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        System.out.println(countWater(num));
    }

    private static int countWater(int[] num) {
        int n = num.length;
        int pre = 0, next = 0;
        int result = 0;
        while (pre < n && next < n) {
            if (num[pre] == 0) {
                pre++;
                continue;
            }
            while (num[next] <= num[pre] && next < n - 1) {
                next++;
            }
            if (num[next] >= num[pre]) {
                result = result + (num[pre] * (next - pre));
                for (int i = pre; i < next; i++) {
                    result -= num[i];
                }
                pre = next;
                next = pre + 1;
            } else {
                int k = next - pre;
                int[] newnum = new int[k];
                for (int i = 0; i < k; i++) {
                    newnum[i] = num[pre + 1];
                    pre++;
                }
                result += countWater(newnum);
            }
        }
        return result;
    }
}
